import { assert_eq, assert } from "./helper"

// https://leetcode-cn.com/problems/search-in-rotated-sorted-array/submissions/
function search(nums: number[], target: number): number {

    const rotated_point = find_rotated_point(nums)

    if (target >= nums[0] && rotated_point !== 0) {
        return bin_search(nums.slice(0, rotated_point), target)
    } else {
        let ret = bin_search(nums.slice(rotated_point), target)
        if (ret >= 0) return ret + rotated_point
        return -1
    }

}

function bin_search(nums: number[], target: number): number {
    let left = 0
    let right = nums.length - 1
    while (left < right) {
        const mid = Math.floor((left + right) / 2)
        if (nums[mid] === target) {
            return mid
        } else if (target > nums[mid]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if (nums[left] === target) {
        return left
    }
    return -1
}

function find_rotated_point(nums: number[]): number {
    let left = 0
    let right = nums.length - 1
    while (left < right) {
        const mid = Math.floor((left + right) / 2)
        if (nums[mid] >= nums[left]
            && nums[mid] > nums[right]
        ) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

// assert_eq(find_rotated_point([4, 5, 6, 1, 2, 3]), 3)
// assert_eq(find_rotated_point([4, 5, 6, 1, 1, 2, 3]), 3)
// assert_eq(find_rotated_point([4, 5, 6, 6, 1, 1, 2, 3]), 4)
// console.log(bin_search([0, 1, 2, 3, 4, 5], 3), 3, "bin")
let a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
a = [4, 5, 6, 7, 0, 1, 2]

console.log(search([1], 1))
